This video discusses the problems that programmers face with Array Data Structures and the need of coming up with Linked List as the alternative.
This track of the course covers the topic "Linked List".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Linked List.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video discusses the problems that programmers face with Array Data Structures and the need of coming up with Linked List as the alternative.
This video discusses the introductory part of the Linked List Data Structure.
This video talks about implementation of a simple singly linked list with three nodes.
CodeThis video talks about creation of a simple linked list with 3 nodes in Java.
Code:
This video talks about traversal of a linked list from head to last node.
Code:
This video talks of traversal of a linked list from head to last node.
Code:
Implementation of recursive function to print a singly linked list
The video discusses both C++ and Java codes for insert at the beginning of Singly Linked List
Codes:
In this video both C++ and Java codes are discussed to insert a node at the end of linked list
Codes:
This video talks about function to delete first node of linked list.
Codes:
This video talks about deletion of last node of a singly linked list.
Codes:
Approach and implementation of insertion at given position in a singly linked list are discussed
This video talks about finding position of an element in a linked list. This video talks about both iteratative and recursive solutions.
Codes:
This video discusses insertion at the beginning of Doubly Linked List
Codes:
Approach and implementations to insert a node at the beginning of doubly linked list are discussed
Code:
This video discusses reversal of doubly linked list.
This video talks about deleting first node of a given doubly linked list.
Codes:
This video talks about deleting last node of a doubly linked list
Codes:
This video talks about two methods for traversal of a circular linked list in C++.
Codes:
This video talks about two methods of circular linked list traversal in Java.
Codes:
This video talks about two methods.
1) Naive : O(n)
2) Efficient : O(n)
Codes:
This video talks about two methods to insert at the end.
1) Naive : O(n)
2) Efficient : O(1)
Codes:
This video talks about deleting first node of a circular linked list
Codes:
This video talks about deleting kth node of a circular linked list where k is less than or equal to the number of nodes in the list.
Codes:
This video introduces circular doubly linked list. It talks about its advantages and insertion.
Codes:
This video discusses insertion in a sorted linked list. The linked list should remain sorted after insertion.
This is an important interview problem where one needs to find the middle of a linked list of a given linked list.
Codes:
This video discusses the problem on finding the n-th node from the end of a given linked list.
Codes:
This video discusses the problem of reversing a linked list in an iterative manner.
Codes:
This video discusses the problem of reversing a linked list in a recursive manner.
Codes:
In this method a tail recursive solution is discussed to reverse the linked list. This method simply follows the iterative solution.
Codes:
Approach and implementation of a function to remove duplicates from a sorted singly linked list
Two methods are discussed here :
1) Recursive
2) Iterative
Codes:
This video discusses the problem of checking whether a linked list contains any loop or not. We would discuss the four methods involved in detecting loops in a linked list, one more efficient than other.
Codes:
This video discusses the problem of detecting a loop using the method of Floyd cycle detection.
Codes:
This video discusses the problem of detecting and removing a loop from the linked list
Codes:
This is one of the tricky problem asked in an interview where a random address to a node of the linked list is given and the user needs to delete the node of the given address. The address can point to any random node in-between a linked list.
Codes:
Given a singly linked list, the task is to segregate or separate the even and odd nodes of the linked list.
Codes:
Intersection of two linked list new
Codes:
Pairwise swap nodes of linked list
Codes:
Clone a linked list using a random pointer
Codes:
LRU Cache Design Discussion using Naive and Efficient Implementation
Codes:
A O(m+n) time and O(1) auxiliary space solution is discussed.
Codes:
Palindrome Linked List
Codes:
Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.

id[] = [1000, 1010, 1050, 2000, 2040].And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000). Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
Representation of Linked Lists
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head node of the list. If the linked list is empty, then the value of the head node is NULL.struct NodeIn Java, LinkedList can be represented as a class, and the Node as a separate class. The LinkedList class contains a reference of the Node class type.
{
int data;
struct Node* next;
};
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) {data = d;}
}
}
1 2 3
Given the head node of a linked list, the task is to insert a new node in this already created linked list.



Given the head pointer pointing to the Head of a singly linked list and a node to be deleted from the list. Delete the given node from the Linked List.

// Find next node using next pointer
struct Node *temp = node_ptr->next;
// Copy data of next node to this node
node_ptr->data = temp->data;
// Unlink next node
node_ptr->next = temp->next;
// Delete next node
free(temp);

Creating and Traversing a Doubly Linked List
Creating and Traversing a doubly linked list is almost similar to that of the singly linked lists. The only difference is that in doubly linked lists we need to maintain an extra previous pointer for every node while creating the list.Created DLL is:
Traversal in forward direction
6 7 1 4
Traversal in reverse direction
4 1 7 6

A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.


Why have we taken a pointer that points to the last node instead of first node?
For insertion of node in the beginning we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of start pointer we take a pointer to the last node then in both the cases there won’t be any need to traverse the whole list. So, insertion in the begging or at the end takes constant time irrespective of the length of the list.6 4 2 8 12 10
Input: Head of following linked listThree Pointers Solution : We will be using three auxiliary three pointers prev, current and next to reverse the links of the linked list. The solution can be understood by the below animation, how links are reversed.
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

void reverse(Node* head)
{
// Initialize current, previous and
// next pointers
Node *current = head;
Node *prev = NULL, *next = NULL
while (current != NULL)
{
// Store next
next = current->next
// Reverse current node's pointer
current->next = prev
// Move pointers one position ahead.
prev = current
current = next
}
head = prev
}
void reverse(Node* head)
{
// Initialize current, previous and
// next pointers
Node *current = head;
Node *prev = NULL, *next = NULL
while (current != NULL)
{
// Store next
next = current->next
// Reverse current node's pointer
current->next = prev
// Move pointers one position ahead.
prev = current
current = next
}
head = prev
}
Node* reverse(Node* node)
{
if (node == NULL) :
return NULL
if (node->next == NULL) :
head = node
return node
Node* temp = reverse(node->next)
temp->next = node
node->next = NULL
return node
}
Hashing Solution :Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.bool detectLoop(Node* h)
{
seen //HashMap
while (h != NULL)
{
// If this node is already present
// in hashmap it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (seen.find(h) == True)
return true
// If we are seeing the node for
// the first time, insert it in hash
seen.insert(h)
h = h->next
}
return false
}
bool detectloop(Node* head)
{
Node *slow_p = head, *fast_p = head
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next
fast_p = fast_p->next->next
if (slow_p == fast_p)
return true
}
return false
}

/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode( Node* head1, Node* head2)
{
c1 = getCount(head1)
c2 = getCount(head2)
d // difference
if(c1 > c2)
d = c1 - c2
return utility(d, head1, head2)
else :
d = c2 - c1
return utility(d, head2, head1)
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int utility(d, Node* head1, Node* head2)
{
Node* current1 = head1
Node* current2 = head2
for ( i = 0 to d-1 )
{
if(current1 == NULL)
return -1
current1 = current1->next
}
while(current1 != NULL && current2 != NULL)
{
if(current1 == current2)
return current1->data
current1= current1->next
current2= current2->next
}
return -1
}
A | Insertion Sort |
B | Quick Sort |
C | Heap Sort |
D | Merge Sort |